題目

題目大意

給一個長度最多 2e4 的陣列，求陣列中任意兩數的 xor 的值的最大值。

想法

經典 trie 應用題，印象中大學資料結構課不會教 trie，所以我稍微解釋一下。
trie 是所謂的字典樹，假如現在有一本字典，裡面的字涵蓋 {“aab”, “abc”, “abba”, “acd”, “bac”, “bbc”}，畫成字典樹會是：

基本上就是前綴一樣的話不會長出點，如果沒有這個字母的話也不會有那個節點的一顆樹。
講解完 trie 了，如果今天我們把字母集合改成 {0, 1} 呢？題目的數字範圍可以看出來，每個數字可以用 31 個 bit 去表示，我們從最前面的 bit 開始建立的話去建字典樹。
以第一個範測 [3,10,5,25,2,8] 為例子，因為 31 個 bit 太多了，我只畫 5 個 bit，分別的二進位值為 [0b00011, 0b01010, 0b00101, 0b11001, 0b00010, 0b01000]，做出來的字典樹為：

接下來我們只要對每個數字都去找一次最大 xor 值就可以收工了，例如 10 (01010) 要找最大 xor 值，第一個 bit 發現有 1，所以第一個 bit = 1，第二個 bit 找不到 0，所以第二個 bit = 0 (但走的節點會是1 喔)，第三個 bit 找不到 1，所以是 0，第四個 bit 找到 0，所以是 1，第五個 bit 有 1 所以是 1，於是得到 10 的最大 xor 值為 0b10011 = 19。
一開始建 tree 會是每個數字的每個 bit 都走一次，後面 query 也是對每個數字來說都走一次每個 bit，所以時間複雜度為 O(N * 31)。
空間複雜度部分最糟糕的情況是每個數字都需要 new 節點，但因為 N 並不會到 2^31 個數字那麼多，所以實際上最糟糕是 O(N * 31)。

Code(C++)

class Node {
public:
    Node *node[2];
    Node() {
        node[0] = node[1] = NULL;
    }
    ~Node() {
        for(int i=0; i<2; i++) {
            if (node[i]) delete node[i];
        }
    }
    void insert(int n) {
        Node *cur = this;
        for(int i=31; i>=0; i--) {
            bool b = n & (1 << i);
            if (!cur->node[b]) cur->node[b] = new Node();
            cur = cur->node[b];
        }
    }
    int query(int n) {
        Node *cur = this;
        int res = 0;
        for(int i=31; i>=0; i--) {
            bool b = n & (1 << i);
            if (!cur->node[!b]) cur = cur->node[b];
            else {
                cur = cur->node[!b];
                res |= 1 << i;
            }
        }
        return res;
    }
};
 
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) { 
        Node *root = new Node();
        for(int i: nums) root->insert(i);
        int ans = 0;
        for(int i: nums) ans = max(ans, root->query(i));
        return ans;
    }
};

心得

這題雖然是 medium，但我記得競賽遇到的時候，滅了不少隊伍的樣子(包括當時的我)，總之是很值得寫的 trie 題！
今天的題目是有人問我的，不是 pick one，如果有希望我明天寫哪一題的話可以留言，我會寫的XD